COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.Sec(Symbolic expressions,Symbolic expressions)
C00005 00003	.<<Examples: s-exprs not sexprs>>
C00008 ENDMK
C⊗;
.Sec(Symbolic expressions,Symbolic expressions)

Our primitive domain consists of objects called ⊗→atoms↔← or ⊗→atomic symbols↔←.
In computer science terminolgy they are either identifiers or ⊗→numbers↔←; i.e.
.GROUP SKIP 2;
.BEGIN TABIT1(13);
.GROUP;
<atom>\:: = <identifier>|<number>
<identifier>\:: = <letter>|<identifier><letter>|<identifier><digit>
<number>\:: = <digit>|<number><digit>
<letter>\:: =%3 A |B |C ...| Z%*
<digit>\:: = %30 |1 |2 ... |9%*
.APART;
.END;
.GROUP SKIP 2;
.BEGIN TABIT2(20,35);DOUBLE SPACE;
.GROUP;
For example:\atoms\not atoms
%3\ABC123\2a
\12\a
\A4D6\$$g
\NIL\ABD.
\T\(A . B)
%*
.APART;
.END;

Most of our discussions will deal with non-numeric atoms. From the point
of view of data structure, numbers are not very interesting. Most implementations
of LISP do however include a large arithmetic entourage.

Using an operator to be described later, we are able to enlarge on
this primitive domain obtaining the domain of interest for LISP functions,
that is the class of %6⊗→symbolic expressions↔←%* or %6⊗→S-expressions↔←%* or also called
%6⊗→S-exprs↔←%*.  S-exprs include as a proper subset the atoms, but S-exprs can be
constructed of other S-exprs as follows:  a left-paren followed by an
S-expr, followed by a period, followed by an S-expr,
followed by a right-paren is also an S-expr.
Non-atomic sexpressions are also called %2⊗→dotted-pairs↔←%*.
To make everyone happy here's a BNF description of S-expressions.
.TURN ON "←";

←<sexpr> :: = <atom>|%3(%*<sexpr> . <sexpr>%3) |( )%*

.TURN OFF "←";
We added "%3( )%*" as an S-expr for a reason which will become clear later.

Notice that if we allow decimal numbers  as atoms some care needs to be
exercised when writing sexpressions. How should %3(A.1.2)%* be interpreted.
Is it the dotted pair %3(A . 1.2)%*, or is it just an ill-formed expression?
.<<Examples: s-exprs not sexprs>>
.BEGIN TABIT2(20,40);
.GROUP;
Examples:\S-exprs\not S-exprs
%3
\A\A . B
\(A . B)\(A . B . C)
\(((A.B) .C) . (A.B))\((A . B)))
%*
.APART;
.END;
.SS(Binary trees)
S-exprs have a natural
interpretation as %6⊗→binary trees↔←%*.  A binary tree is a branching structure 
consisting of a single root node and perhaps a collection of terminal
and non-terminal nodes.  From non-terminal nodes we sprout exactly two
branches; no branches are grown from the terminal nodes.  And most
important:  there are no intersecting branches.  We will talk about more
general structures later (called list-structures or directed graphs).
.GROUP SKIP 2;
.GROUP;
Here are some binary trees:

.BEGIN TABIT2(5,40);SELECT 3;

					.		   
.GROUP SKIP 8;
\1    2       A   D   E\A    B    NIL

.END


.APART;
%1
Perhaps you can see how to interpret S-exprs now.  The atoms are
interpreted as terminal nodes;  and since non-atomic S-exprs always
have two sub-expressions we can write the first
sub-expression as the left branch of a binary tree and the second sub-
expression as the right branch.  
.GROUP SKIP 2;
.GROUP;
For example:

.BEGIN TABIT2(10,40);SELECT 3;

\(A . B)\(A . (B . C))
.GROUP SKIP 5;
\A   B\A    B    C

.APART;